package Hard;

import java.util.ArrayList;
import java.util.List;

// 51.N皇后问题
// 思路：两个临时数组，一个用来记录永远不能再使用的数字，一个用来存放下一步的时候不能使用的数字。
public class Solution51 {
    public List<List<String>> solveNQueens(int n) {
        List<Integer> forEver = new ArrayList<>();
        List<Integer> next = new ArrayList<>();
        List<List<String>> resList = new ArrayList<>();
        dfs(resList, forEver, next, n);

        return resList;
    }

    public void dfs(List<List<String>> resList, List<Integer> forEver, List<Integer> next, int n) {
        //寻找有没有还能放入的数，有的话则dfs，没有的话看看forEver.size()==n是否成立，成立则创建list加入到resList，否则递归结束
        for (int i = 0; i < n; i++) {
            if (forEver.contains(i) || next.contains(i))
                continue;
            forEver.add(i);
            List<Integer> newNext = new ArrayList<>();
//            newNext.add(i - 1);
//            newNext.add(i + 1);
            //要加入next中能使两个皇后构成一条斜线的边的顶点，不只是上一个顶点的+1和-1
            Integer arr[] = new Integer[forEver.size()];
            forEver.toArray(arr);
            for (int j = 1, k = arr.length - 1; k > -1; j++, k--) {
                newNext.add(arr[k]-j);
                newNext.add(arr[k]+j);
            }
            dfs(resList, forEver, newNext, n);
            forEver.remove(forEver.size() - 1);
        }
        if (forEver.size() == n) {
            List<String> list = new ArrayList<>();
            Integer[] forEverArr = new Integer[n];
            forEver.toArray(forEverArr);
            for (int i = 0; i < n; i++) {
                char[] chars = new char[n];
                //写入Q
                chars[forEverArr[i]] = 'Q';
                //写入.
                for (int j = 0; j < n; j++) {
                    if (j != forEverArr[i])
                        chars[j] = '.';
                }
                //转换为字符串，加入到结果中
                String str = new String(chars);
                list.add(str);
            }
            resList.add(list);
        }
    }

    public static void main(String[] args) {
        Solution51 s = new Solution51();
        s.solveNQueens(4);
    }
}
